package org.basis.algorithm.greedy;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.Collections;
import java.util.List;

/**
 * 求集合交集测试
 *
 * @author Mr_wenpan@163.com 2021/12/27 17:46
 */
public class IntersectionTest {

    public static void main(String[] args) {
//        retainAllByBitSet();
        retainAll();

        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();

        list1.add(1);
        list1.add(2);
        list1.add(3);

        list2.add(2);
        list2.add(3);
        list2.add(3);
        list2.add(3);
        list2.add(3);
        list2.add(4);

        List<Integer> list = retainAllByPoint(list1, list2);
        System.out.println("list = " + list);
    }

    /**
     * 双指针求交集
     */
    private static List<Integer> retainAllByPoint(List<Integer> list1, List<Integer> list2) {
        if (list1 == null || list2 == null) {
            return null;
        }
        // 排升序
        Collections.sort(list1);
        Collections.sort(list2);

        int first = 0;
        int second = 0;
        List<Integer> res = new ArrayList<>();

        while (first != list1.size() && second != list2.size()) {
            // 第一个大那么第二个往前走
            if (list1.get(first) > list2.get(second)) {
                second++;
            } else if (list1.get(first) < list2.get(second)) {
                first++;
            } else {
                res.add(list1.get(first));
                first++;
                second++;
            }
        }

        // 第一个指针没有走到边界
        while (first != list1.size()) {
            if (!list1.get(first).equals(list2.get(second - 1))) {
                break;
            }
            res.add(list1.get(first));
            first++;
        }

        // 第二个指针没有走到边界
        while (second != list2.size()) {
            if (!list2.get(second).equals(list1.get(first - 1))) {
                break;
            }
            res.add(list2.get(second));
            second++;
        }

        return res;
    }

    private static void retainAll() {
        List<Integer> txtList = new ArrayList<>();
        List<Integer> txtList2 = new ArrayList<>();

        txtList.add(1);
        txtList.add(2);
        txtList.add(3);

        txtList2.add(2);
        txtList2.add(3);
        txtList2.add(3);
        txtList2.add(3);
        txtList2.add(4);

        // txtList.retainAll(txtList2) 会使得txtList里只有交集里的数据，如果没有交集，那么txtList会被抹为空
        // 交集会被去重
        boolean flg = txtList.retainAll(txtList2);
        System.out.println("txtList = " + txtList);
        System.out.println("txtList2 = " + txtList2);
        System.out.println("flg = " + flg);
    }

    /**
     * 利用bitmap求两个list的交集
     */
    private static void retainAllByBitSet() {
        List<Integer> txtList = new ArrayList<>();
        List<Integer> txtList2 = new ArrayList<>();

        txtList.add(1);
        txtList.add(2);
        txtList.add(3);

        txtList2.add(2);
        txtList2.add(3);
        txtList2.add(4);

        long begin = System.currentTimeMillis();

        BitSet bitSet = new BitSet(Collections.max(txtList));
        BitSet bitSet1 = new BitSet(Collections.max(txtList2));

        for (int i = 0; i < txtList.size(); i++) {
            bitSet.set(txtList.get(i));
        }

        for (int i = 0; i < txtList2.size(); i++) {
            bitSet1.set(txtList2.get(i));
        }

        bitSet.and(bitSet1);
        long end = System.currentTimeMillis();

        System.out.println("bitSet方法耗时:" + (end - begin));
        System.out.println("交集的个数为:" + bitSet.cardinality());
    }
}
